package LeetCode.month01.day31;

public class No1277 {
    public static void main(String[] args) {
        System.out.println(countSquares(new int[][]{
                {0,1,1,1},
                {1,1,1,1},
                {0,1,1,1}

        }));
    }
    public static int countSquares(int[][] matrix) {
        //前缀和
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] presum = new int[m+1][n+1];
        for (int i = 1; i<= m; i++) {
            for (int j = 1; j <= n; j++) {
                presum[i][j] = presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+matrix[i-1][j-1];
            }
        }
        int count = 0;
        int maxsize = Math.min(m,n);
        for (int size = 1; size <= maxsize; size++) {
            for (int i = 0; i <= m-size; i++) {
                for (int j = 0; j <= n-size; j++) {
                    int area = presum[i+size][j+size]-presum[i+size][j]-presum[i][j+size]+presum[i][j];
                    if(area==size*size) count++;
                }
            }
        }
        return count;


        //动态规划
//        int m = matrix.length;
//        int n = matrix[0].length;
//        int[][] dp = new int[m][n];
//        int num = 0;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if(matrix[i][j]==0) dp[i][j]=0;
//                else{
//                    if(i==0||j==0) dp[i][j]=1;
//                    else{
//                        dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
//                    }
//                    num+=dp[i][j];
//                }
//            }
//        }
        //return num;


    }
}
